#include <stdio.h>
#include <assert.h>

int naive_search(int query, int* data, int data_len)
{
    int i = 0;

    for (i=0; i<data_len; i++) 
    {
        if (data[i] == query)
            break;
    }
    
    int index = (i<data_len) ? i : -1;
    return index;
    /*
    if (i<data_len) return i;
    assert(i == data_len); */
    return -1;
}

/*
 * we assume data has been sorted in ascending order.
 */
int binary_search(int query, int* data, int data_len)
{
    /* start and end define the search range */
    int start = 0;
    int end = data_len-1;
    
    while (start <= end)
    {   
        int middle = (end+start)>>1;
        //printf("%d -> %d -> %d, middle %d\n", start, middle, end, data[middle]);

        if (data[middle] == query) return middle;
        else if (data[middle] > query) end = middle - 1;
        else start = middle + 1;
        //if (data[middle] < query) start = middle + 1;
    }
    return -1;
}

int main()
{
    int data[] = {1, 5, 7, 10, 11};
    int data_len = 5;
    int query[] = {1, 5, 0, 11};
    int query_len = 4;

    for (int i=0; i<query_len; i++)
    {
        int index = naive_search(query[i], data, data_len);
        printf("index of %d -> %d\n", query[i], index);
        int fast = binary_search(query[i], data, data_len);
        printf("index of %d -> %d\n", query[i], fast);
        assert(index == fast);
    }
    return 0;
}
